//You are visiting a farm that has a single row of fruit trees arranged from 
//left to right. The trees are represented by an integer array fruits where fruits[i]
// is the type of fruit the iᵗʰ tree produces. 
//
// You want to collect as much fruit as possible. However, the owner has some 
//strict rules that you must follow: 
//
// 
// You only have two baskets, and each basket can only hold a single type of 
//fruit. There is no limit on the amount of fruit each basket can hold. 
// Starting from any tree of your choice, you must pick exactly one fruit from 
//every tree (including the start tree) while moving to the right. The picked 
//fruits must fit in one of your baskets. 
// Once you reach a tree with fruit that cannot fit in your baskets, you must 
//stop. 
// 
//
// Given the integer array fruits, return the maximum number of fruits you can 
//pick. 
//
// 
// Example 1: 
//
// 
//Input: fruits = [1,2,1]
//Output: 3
//Explanation: We can pick from all 3 trees.
// 
//
// Example 2: 
//
// 
//Input: fruits = [0,1,2,2]
//Output: 3
//Explanation: We can pick from trees [1,2,2].
//If we had started at the first tree, we would only pick from trees [0,1].
// 
//
// Example 3: 
//
// 
//Input: fruits = [1,2,3,2,2]
//Output: 4
//Explanation: We can pick from trees [2,3,2,2].
//If we had started at the first tree, we would only pick from trees [1,2].
// 
//
// 
// Constraints: 
//
// 
// 1 <= fruits.length <= 10⁵ 
// 0 <= fruits[i] < fruits.length 
// 
// Related Topics Array Hash Table Sliding Window 👍 578 👎 28


package leetcode.editor.en;

import java.util.HashMap;
import java.util.Map;

public class _904_FruitIntoBaskets {
    public static void main(String[] args) {
        Solution solution = new _904_FruitIntoBaskets().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int totalFruit1(int[] fruits) {
            int l = 0, r = 0, type = 0, max = Integer.MIN_VALUE;
            Map<Integer, Integer> map = new HashMap<>();
            while (r<fruits.length){
                if (!map.containsKey(fruits[r])) {
                    map.put(fruits[r], 0);
                }
                Integer i = map.get(fruits[r]);
                if (i==0){
                    type++;
                }
                map.put(fruits[r], i+1);
                if (type<=2){
                    max = Math.max(max, r-l+1);
                }
                while (type>2){
                    Integer j = map.get(fruits[l]);
                    map.put(fruits[l], j-1);
                    if (j-1 ==0) {
                        type--;
                    }
                    l++;
                }
                r++;
            }
            return max == Integer.MIN_VALUE ? 0:max;
        }





        public int totalFruit(int[] fruits) {
            int l = 0, type = 0, result = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int r = 0; r < fruits.length; r++) {
                if (!map.containsKey(fruits[r]) || map.get(fruits[r]) == 0) {
                    map.put(fruits[r], 0);
                    type++;
                }
                map.put(fruits[r], map.get(fruits[r])+1);
                if (type<=2){
                    result = Math.max(result, r-l+1);
                }
                while (type>2 && l < fruits.length){
                    Integer i = map.get(fruits[l]);
                    map.put(fruits[l], i-1);
                    if (i-1 == 0) {
                        type --;
                    }
                    l++;
                }
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}